//
// Created by Vincent-Vic on 2020/3/11.
//


#include "CMap.h"

//初始化图
CMap::CMap(int capacity){

    m_iCapacity = capacity;
    m_iNodeCount = 0;
    m_pNodeArray = new Node[m_iCapacity];
    m_pMatrix = new int[m_iCapacity * m_iCapacity];
    //初始化内存空间
    memset(m_pMatrix,0,m_iCapacity*m_iCapacity* sizeof(int));
}

//图的析构函数
CMap::~CMap() {
    delete m_pNodeArray;
    m_pNodeArray = nullptr;
    delete m_pMatrix;
    m_pMatrix = nullptr;
}

//图添加节点
bool CMap::addNode(Node *pNode) {
    if (m_iNodeCount>=m_iCapacity || pNode == NULL || isEmpty())
        return false;
    m_pNodeArray[m_iNodeCount].setMCData(pNode->getMCData());
    m_iNodeCount++;
    return true;
}

//重置节点
void CMap::resetNode() {
    for (int i = 0; i < m_iNodeCount; ++i) {
        m_pNodeArray[i].setMBIsVisited(false);
    }
}

//为有向图设置邻接矩阵
bool CMap::setValueToMatrixForDirectedGraph(int row, int col, int val) {
    if (row < 0 ||row >= m_iCapacity || col < 0 || col >= m_iCapacity )
        return false;
    m_pMatrix[row * m_iCapacity + col] = val;
    return true;
}

//为无向图设置邻接矩阵
bool CMap::setValueToMatrixForUndirectedGraph(int row, int col, int val) {
    if (row < 0 ||row >= m_iCapacity || col < 0 || col >= m_iCapacity )
        return false;
    m_pMatrix[row * m_iCapacity + col] = val;
    m_pMatrix[col * m_iCapacity + row] = val;
    return true;
}

//从矩阵中获取权值
bool CMap::getValueFromMatrix(int row, int col, int &val) {
    if (row < 0 ||row >= m_iCapacity || col < 0 || col >= m_iCapacity )
        return false;
    val = m_pMatrix[row * m_iCapacity + col];
    return true;
}

//深度优先遍历
void CMap::depthFirstTraverse(int nodeIndex) {
    int value = 0;
    cout<<m_pNodeArray[nodeIndex].getMCData()<<" ";
    m_pNodeArray[nodeIndex].setMBIsVisited(true);

    for (int i = 0; i < m_iCapacity; ++i) {
        getValueFromMatrix(nodeIndex,i,value);
        if(value == 1 ){    //如果节点存在
            if (m_pNodeArray[i].isMBIsVisited()){   //如果被访问过
                continue;
            } else{
                depthFirstTraverse(i);  //没有被访问继续递归
            }
        } else{
            continue;
        }
    }
}

//广度优先遍历
void CMap::breadthFirstTraverse(int nodeIndex) {
    //先遍历当前节点
    cout<<m_pNodeArray[nodeIndex].getMCData()<<" ";
    m_pNodeArray[nodeIndex].setMBIsVisited(true);

    //存放当前节点
    vector<int> curVec;
    curVec.push_back(nodeIndex);

    //进一步广度优先遍历
    breadthFirstTraverseImpl(curVec);
}

//广度优先遍历实现函数
void CMap::breadthFirstTraverseImpl(vector<int> preVec) {
    int value = 0;
    vector<int> curVec;
    for (int item:preVec) {
        for (int i = 0; i < m_iCapacity ; ++i) {
            getValueFromMatrix(item,i,value);
            if (value != 0){
                if (!m_pNodeArray[i].isMBIsVisited()){
                    cout<<m_pNodeArray[i].getMCData()<<" ";
                    m_pNodeArray[i].setMBIsVisited(true);
                    curVec.push_back(i);
                } else{
                    continue;
                }
            }
        }
    }

    if (curVec.size() == 0 ){
        return;
    } else{
        breadthFirstTraverseImpl(curVec);
    }
}

//打印邻接矩阵
void CMap::printMatrix() {
    for (int i = 0; i < m_iCapacity; ++i) {
        for (int j = 0; j < m_iCapacity; ++j) {
            cout<<m_pMatrix[i*m_iCapacity + j ]<< "  ";
        }
        cout<<endl;
    }
}





//判断图是否为空
bool CMap::isEmpty() {
    return m_iCapacity == 0 ;
}
